/**
 * 
 */
package edu.umd.clip.lm.util;

import java.util.*;

/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class RandomizedQueue<E> extends AbstractQueue<E> {
	private ArrayList<E> data;
	private Random rnd = new Random();
	private int lastPosition = -1; // records the last peek position, so that consequent peek() or poll() return the same element
	
	/**
	 * 
	 */
	public RandomizedQueue() {
		super();
		data = new ArrayList<E>();
	}
	
	/**
	 * @param data
	 */
	public RandomizedQueue(ArrayList<E> data) {
		this.data = data;
	}

	/* (non-Javadoc)
	 * @see java.util.AbstractCollection#iterator()
	 */
	@Override
	public Iterator<E> iterator() {
		throw new UnsupportedOperationException();
	}

	/* (non-Javadoc)
	 * @see java.util.AbstractCollection#size()
	 */
	@Override
	public int size() {
		return data.size();
	}

	/* (non-Javadoc)
	 * @see java.util.Queue#offer(java.lang.Object)
	 */
	@Override
	public boolean offer(E e) {
		return data.add(e);
	}

	/* (non-Javadoc)
	 * @see java.util.Queue#peek()
	 */
	@Override
	public E peek() {
		if (data.size() == 0) return null;
		return data.get(getNextPosition()); 
	}

	/* (non-Javadoc)
	 * @see java.util.Queue#poll()
	 */
	@Override
	public E poll() {
		if (data.size() == 0) return null;
		int pos = getNextPosition();
		E e = data.get(pos);
		if (pos < data.size() - 1) {
			data.set(pos, data.get(data.size()-1));
		}
		data.remove(data.size()-1);
		lastPosition = -1;
		return e;
	}

	public void drainTo(Collection<E> dest) {
		while(true) {
			E e = poll();
			if (e == null) return;
			dest.add(e);
		}
	}
	
	private int getNextPosition() {
		if (lastPosition >= 0) return lastPosition;
		lastPosition = rnd.nextInt(data.size());
		return lastPosition;
	}
}
